/**
 * 该模块实现了一个高性能无序 Set 集合。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */

module system.collections.HashSet;

import system.collections.IEnumerable;
import system.collections.IEnumerator;
import system.collections.ICollection;
import system.collections.IEqualityComparer;
import system.collections.EqualityComparer;
import system.collections.Exception;

import PrimeHelper = system.collections.PrimeHelper;

import system.Traits;
import system.Exception;
import system.BitArray;
import HashHelper = system.Hash;
import system.Array;

version(unittest)
{
	import system.collections.ArrayList;
}

/**
 * 表示一个高性能无序 Set 集合。
 * Comments:
 *		它不保证 Set 的迭代顺序；特别是它不保证该顺序恒久不变。
 *		此类允许使用 null 元素。
 *		HashSet(T) 基于数学 Set 模型，并提供多种数学 Set 运算。
 *		比如，差集，并集，交集，余集等。
 *		此外，它还提供了一些方法，用于确定两个 Set 是否相等，重叠，
 *		以及一个 Set 是否另一个 Set 的子集还是超集。
 */

public class HashSet(T) : IEnumerable!(T), ICollection!(T)
{
	package struct Slot
	{
		hash_t hashCode;
		int next;
		T value;
	}

	private IEqualityComparer!(T) theComparer;
	private int[] theBuckets;
	private Slot[] theSlots;
	private int theSize;
	private int theFreeList;
	private int theFreeSize;
	private int theVersion;

	/**
	 * 初始化 HashSet(T) 类的一个新实例，该实例为空并使用集类型的指定相等比较器。
	 * Params:
	 *		comparer = 指定的相等比较器。
	 *		默认情况下使用 DefaultEqualityComparer(T) 。
	 * Throws:
	 *		AssertError，当比较器为 null 时。
	 * Comments:
	 *		此构造函数的运算复杂度为 O(1)。 
	 */
	public this(IEqualityComparer!(T) comparer = DefaultEqualityComparer!(T).getInstance())
	in
	{
		assert(comparer !is null);
	}
	body
	{
		theComparer = comparer;
		theFreeList = -1;
	}

	/**
	 * 初始化 HashSet(T) 类的一个新实例，该实例为空并使用集类型的指定相等比较器和指定初始容量。
	 * Params:
	 *		capacity = 指定的初始容量。
	 *		comparer = 指定的相等比较器。
	 *		默认情况下使用 DefaultEqualityComparer(T) 。
	 * Throws:
	 *		AssertError，当比较器为 null 或指定的初始容量小于 0 时。
	 * Comments:
	 *		此构造函数的运算复杂度为 O(1)。 
	 */
	public this(int capacity, IEqualityComparer!(T) comparer = DefaultEqualityComparer!(T).getInstance())
	in
	{
		assert(capacity >= 0 && capacity <= int.max);
		assert(comparer !is null);
	}
	body
	{
		theComparer = comparer;
		theFreeList = -1;
		initialize(capacity);
	}

	/**
	 * 初始化 HashSet(T) 类的一个新实例，该实例使用集类型的默认相等比较器，
	 * 和包含从指定的集合复制的元素，并且有足够的容量容纳所复制的这些元素。 
	 * Params:
	 *		collection = 其元素被复制到新集中的集合。
	 * Throws:
	 *		AssertError，当 collection 为 null 时。
	 * Comments:
	 *		此构造函数的运算复杂度为 O(n)，其中 n 是 collection 中的元素数。 
	 */
	public this(IEnumerable!(T) collection)
	in
	{
		assert(collection !is null);
	}
	body
	{
		this(collection, DefaultEqualityComparer!(T).getInstance());
	}

	/**
	 * 初始化 HashSet(T) 类的一个新实例，该实例使用集类型的指定相等比较器，
	 * 和包含从指定的集合复制的元素，并且有足够的容量容纳所复制的这些元素。
	 * Params:
	 *		collection = 其元素被复制到新集中的集合。
	 *		comparer = 指定的相等比较器。
	 * Throws:
	 *		AssertError，当 collection 或 comparer 为 null 时。
	 * Comments:
	 *		此构造函数的运算复杂度为 O(n)，其中 n 是 collection 中的元素数。 
	 */
	public this(IEnumerable!(T) collection, IEqualityComparer!(T) comparer)
	in
	{
		assert(collection !is null);
		assert(comparer !is null);
	}
	body
	{
		this(comparer);
		auto size = 0;
		auto currentCollection = cast(ICollection!(T))collection;
		if(currentCollection !is null)
		{
			size = currentCollection.count;
		}
		initialize(size);
		foreach(item; collection)
		{
			this.add(item);
		}
		if((theSize == 0 && theSlots.length > PrimeHelper.PrimeArray[0]) || (theSize > 0 && (theSlots.length / theSize) > 3))
		{
			trimExcess();
		}
	}

	/*
	 * 实现 ICollection(T) 接口。
	 */

	/**
	 * 查看该 Set 是否为空。
	 * Returns:
	 *		如果该 Set 为空，返回 true ；否则，返回 false 。
	 */
	public final bool isEmpty()
	{
		return theSize is 0;
	}

	/**
	 * 获取该 Set 包含的元素数。
	 */
	public final int count()
	{
		return theSize;
	}

	/**
	 * 查看该 Set 是否只读。
	 * Returns:
	 *		返回 false 。
	 */
	public final bool isReadOnly()
	{
		return false;
	}

	/**
	 * 将指定的元素添加到 HashSet(T) 中。
	 * Params: 
	 *		item = 要添加到 Set 中的元素。
	 * Returns:
	 *		如果该元素添加到 HashSet(T) 中为 true；如果该元素已存在则为 false。
	 * Comments:
	 *		如果 count 已等于 HashSet(T) 的容量，则会自动调整该容量以容纳新项。
	 *		如果 count 小于内部数组的容量，则此方法的运算复杂度为 O(1)。
	 *		如果必须调整 HashSet(T) 的大小，则此方法的运算复杂度将为 O(n)，其中 n 是 count。 
	 */
	public final bool add(T item)
	{
		int freeList;
		if(theBuckets is null)
		{
			initialize(3);
		}
		//计算该元素的哈希值和在哈希表内的索引位置
		auto hash = hashOf(item);
		auto index = hash % theBuckets.length;
		
		//查找是否哈希表内已经有该元素
		for(auto i = theBuckets[index] - 1; i >= 0; i = theSlots[i].next)
		{
			if(theSlots[i].hashCode == hash && theComparer.equals(theSlots[i].value, item))
			{
				return false;
			}
		}

		//到了这里，表明哈希表内没有该元素
		//但是引起了哈希表散列冲突
		if(theFreeList >= 0)
		{
			//查找元素放入链表的适当位置
			freeList = theFreeList;
			theFreeList = theSlots[freeList].next;
		}
		else	//没有引起哈希表散列冲突
		{
			//查看是否满载，是否需要扩容
			if(theFreeSize == theSlots.length)
			{
				resize();
				index = hash % theBuckets.length;
			}
			freeList = theFreeSize;
			theFreeSize++;
		}
		//把元素放入哈希表内
		//并设置合适的值
		theSlots[freeList].hashCode = hash;
		theSlots[freeList].next = theBuckets[index] - 1;
		theSlots[freeList].value = item;

		theBuckets[index] = freeList + 1;

		theSize++;
		theVersion++;
		return true;
	}

	/**
	 * 清空此 HashSet(T)，并且对该集合所有元素的引用也释放。
	 * Comments:
	 *		在调用 trimExcess 之前该集合容量会保持不变。
	 *		此方法的运算复杂度为 O(n)，其中 n 为 count。 
	 */
	public final void clear()
	{
		if(theFreeSize > 0)
		{
			Array.clear!(Slot)(theSlots[0..theFreeSize]);
			Array.clear!(int)(theBuckets);
			theSize = 0;
			theFreeSize = 0;
			theFreeList = -1;
		}
		theVersion++;
	}

	/**
	 * 确定 HashSet(T) 对象是否包含指定的元素。
	 * Params:
	 *		item = 要在 HashSet(T) 中查找的元素。 
	 * Returns:
	 *		如果 HashSet(T) 包含指定的元素，为 true；否则为 false。
	 * Comments:
	 *		此方法的运算复杂度为 O(1)。
	 */
	public final bool contains(T item)
	{
		return indexOf(item) != -1;
	}

	/**
	 * 从 HashSet(T) 中移除指定的元素。
	 * Params:
	 *		item = 要移除的元素。
	 * Returns:
	 *		如果成功找到并移除该元素，则为 true；否则为 false。
	 *		如果在 HashSet(T) 对象中找不到 item，则返回 false。
	 * Comments:
	 *		如果 HashSet(T) 不包含指定的元素，则该对象将保持不变。不引发异常。
	 *		此方法的运算复杂度为 O(1)。 
	 */
	public bool remove(T item)
	{
		if(theBuckets !is null)
		{
			auto hash = hashOf(item);
			auto index = hash % theBuckets.length;
			auto freeList = -1;
			for(auto i = theBuckets[index] - 1; i >= 0; i = theSlots[i].next)
			{
				if((theSlots[i].hashCode == hash) && (theComparer.equals(theSlots[i].value, item)))
				{
					if(freeList < 0)
					{
						theBuckets[index] = theSlots[i].next + 1;
					}
					else
					{
						theSlots[freeList].next = theSlots[i].next;
					}
					theSlots[i].hashCode = -1;
					theSlots[i].next = theFreeList;
					theSlots[i].value = T.init;
					theFreeList = i;
					theSize--;
					theVersion++;
					return true;
				}
				freeList = i;
			}
		}
		return false;
	}

	/**
	 * 将此 HashSet(T) 的元素复制到数组中。
	 * Params:
	 *		array = 要复制元素的目标数组。
	 * Throws:
	 *		AssertError，当 array 为 null 或 array 的容量小于此 HashSet(T) 时。
	 * Comments:
	 *		此方法的运算复杂度为 O(n)，其中 n 为 count。
	 */
	public final void toArray(T[] array)
	in
	{
		assert(array !is null, "Array can not be null.");
		assert(array.length >= theSize, "Array is too small.");
	}
	body
	{
		auto size = 0;
		for(auto i = 0; i < theFreeSize && size < theSize; i++)
		{
			if(theSlots[i].hashCode >= 0)
			{
				array[size++] = theSlots[i].value;
			}
		}
	}

	/*
	 * 实现 IEnumerable(T) 接口。
	 */

	public final Enumerator getEnumerator()
	{
		return new Enumerator();
	}

	public final int opApply (int delegate (ref T value) dg)
	{
		auto scope enumerator = new Enumerator();
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
	}

	public final class Enumerator : IEnumerator!(T)
	{
		private int theIndex;
		private int modCount;
		private T theValue;

		package this()
		{
			theIndex = 0;
			modCount = theVersion;
			theValue = T.init;
		}

		public bool moveNext()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

			while(theIndex < theFreeSize)
			{
				if(theSlots[theIndex].hashCode >= 0)
				{
					theValue = theSlots[theIndex].value;
					theIndex++;
					return true;
				}
				theIndex++;
			}

			theIndex = theFreeSize + 1;
			theValue = T.init;
			return false;
		}

		public T current()
		{
			return theValue;
		}

		public void reset()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

			theIndex = 0;
			theValue = T.init;
		}
	}

	/*
	 * 其他方法。
	 */

	/**
	 * 返回 IEqualityComparer!(HashSet!(T)) 对象，
	 * 该对象可用于对 HashSet(T) 对象进行深入的相等测试。
	 * Comments:
	 *		调用此方法的运算复杂度为 O(1)。
	 */
	public static IEqualityComparer!(HashSet!(T)) createSetComparer()
	{
		return new HashSetEqualityComparer!(T)();
	}

	/**
	 * 从此 HashSet(T) 中移除指定集合中的所有元素。
	 * Params:
	 *		other = 要移除元素的集合。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		该方法等效于数学上的差集。
	 *		此方法的运算复杂度是 O(n)，其中 n 为 other 参数中的元素个数。
	 */
	public final void exceptWith(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(theSize != 0)
		{
			auto set = cast(HashSet!(T))other;
			if(set !is null)
			{
				if(this == set)
				{
					this.clear();
				}
			}
			else
			{
				foreach(item; other)
				{
					this.remove(item);
				}
			}
		}
	}

	/**
	 * 修改当前的 HashSet(T) ，仅包含该对象和指定集合中存在的元素。
	 * Params:
	 *		other = 要与当前的 HashSet(T) 进行比较的集合。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		此方法等效于数学上的交集。
	 *		如果由 other 参数表示的集合是与当前的 HashSet(T) 有相同的相等比较器的 HashSet(T) 集合，
	 *		则此方法的运算复杂度是 O(n)。
	 *		否则，此方法的运算复杂度是 O(n + m)，其中 n 是 count，m 是 other 中的元素个数。
	 */
	public final void intersectWith(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(other.count == 0)
		{
			this.clear();
			return;
		}
		auto array = new T[theSize];
		this.toArray(array);
		foreach(item; array)
		{
			if(!other.contains(item))
				remove(item);
		}
		foreach(item; other)
		{
			if(!contains(item))
				remove(item);
		}
	}

	/**
	 * 修改当前的 HashSet(T) ，以包含该对象本身和指定集合中存在的所有元素。
	 * Params:
	 *		other = 要与当前的 HashSet(T) 进行比较的集合。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		此方法等效于数学上的并集。
	 *		此方法的运算复杂度是 O(n)，其中 n 为 other 参数中的元素个数。
	 */
	public final void unionWith(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		foreach(item; other)
		{
			this.add(item);
		}
	}

	/**
	 * 修改当前的 HashSet(T) ，
	 * 仅包含该对象或指定集合中存在的元素（但不可同时包含两者中的元素）。
	 * Params:
	 *		other = 要与当前的 HashSet(T) 进行比较的集合。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		此方法等效于数学中的余集。
	 *		此方法的运算复杂度是 O(n)，其中 n 为 other 参数中的元素个数。
	 */
	public final void symmetricExceptWith(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(theSize == 0)
		{
			this.unionWith(other);
		}
		else if(this == cast(HashSet!(T))other)
		{
			this.clear();
		}
		else
		{
			foreach(item; other)
			{
				if(contains(item))
					remove(item);
				else
					add(item);
			}
		}
		
	}

	/**
	 * 从 HashSet(T) 集合中移除与指定的谓词所定义的条件相匹配的所有元素。
	 * Params:
	 *		match = 用于定义要移除的元素应满足的条件。
	 * Returns:
	 *		已从 HashSet(T) 集合中移除的元素个数。
	 * Throws:
	 *		AssertError，当 match 为 null 时。
	 * Comments:
	 *		调用此方法的运算复杂度是 O(n)，其中 n 是 count。
	 */
	public final int removeWhere(bool delegate(T) match)
	in
	{
		assert(match !is null);
	}
	body
	{
		int result = 0;
		for(auto i = 0; i < theFreeSize; i++)
		{
			if(theSlots[i].hashCode >= 0)
			{
				auto item = theSlots[i].value;
				if(match(item) && remove(item))
					result++;
			}
		}
		return result;
	}

	/// ditto
	public final int removeWhere(bool function(T) match)
	in
	{
		assert(match !is null);
	}
	body
	{
		int result = 0;
		for(auto i = 0; i < theFreeSize; i++)
		{
			if(theSlots[i].hashCode >= 0)
			{
				auto item = theSlots[i].value;
				if(match(item) && remove(item))
					result++;
			}
		}
		return result;
	}

	/**
	 * 将 HashSet(T) 的容量设置为它所包含的元素的实际个数，
	 * 向上舍入为接近的特定于实现的值。
	 * Comments:
	 *		如果已知不会再添加新元素，
	 *		可以使用 trimExcess 方法将 HashSet(T) 的内存开销降到最低限度；
	 *		若要彻底清除 HashSet(T) 并释放它引用的所有内存，
	 *		请在调用 Clear 方法后再调用此方法。 
	 *		此方法的运算复杂度为 O(n)，其中 n 为 count。
	 */
	public final void trimExcess()
	{
		if(theSize == 0)
		{
			if(theBuckets !is null)
				delete theBuckets;
			if(theSlots !is null)
				delete theSlots;
			theVersion++;
		}
		else
		{
			auto newPrime = PrimeHelper.getNextPrime(theSize);
			auto newSlots = new Slot[newPrime];
			auto newBuckets = new int[newPrime];
			int index = 0;
			for(auto i = 0; i < theFreeSize; i++)
			{
				if(theSlots[i].hashCode >= 0)
				{
					newSlots[index] = theSlots[i];
					auto bucket = newSlots[index].hashCode % newPrime;
					newSlots[index].next = newBuckets[bucket] - 1;
					newBuckets[bucket] = index + 1;
					index++;
				}
			}
			theFreeSize = index;
			delete theSlots;
			delete theBuckets;
			theSlots = newSlots;
			theBuckets = newBuckets;
			theFreeList = -1;
		}
	}

	/**
	 * 确定当前的 HashSet(T) 是否与指定的集合重叠。
	 * Params:
	 *		other = 要与当前的 HashSet(T) 进行比较的集合。
	 * Returns:
	 *		如果此 HashSet(T) 与 other 至少共享一个公共元素，为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		此方法的运算复杂度是 O(n)，其中 n 为 other 中元素的个数。
	 */
	public final bool overlaps(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(theSize != 0)
		{
			foreach(item; other)
			{
				if(this.contains(item))
					return true;
			}
		}
		return false;
	}

	/**
	 * 确定 HashSet(T) 与指定的集合中是否包含相同的元素。
	 * Params:
	 *		other = 要与当前的 HashSet(T) 进行比较的集合。
	 * Returns:
	 *		如果 HashSet(T) 对象等于 other，为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		此方法的运算复杂度是 O(n)，其中 n 为 count。
	 */
	public final bool setEquals(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(theSize != other.count)
			return false;
		foreach(item; this)
		{
			if(!other.contains(item))
				return false;
		}
		return true;
	}

	/**
	 * 确定此 HashSet(T) 是否为指定集合的真子集。
	 * Params:
	 *		other = 要进行比较的集合。
	 * Returns:
	 *		如果 HashSet(T) 是 other 的真子集，为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		空集是其他任意集合（包括空集）的真子集；
	 *		因此，如果由当前的 HashSet(T) 表示的集合为空，此方法返回 true，即使 other 参数为空集也是如此。
	 *		如果 count 大于或等于 other 中元素的个数，则此方法始终返回 false。
	 *		此方法的运算复杂度是 O(n)。
	 */
	public final bool isProperSubsetOf(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(theSize == 0)
			return other.count > 0;
		if(theSize >= other.count)
			return false;
		return checkIsSubsetOf(other);
	}

	/**
	 * 确定此 HashSet(T) 是否为指定集合的子集。
	 * Params:
	 *		other = 要进行比较的集合。
	 * Returns:
	 *		如果 HashSet(T) 是 other 的子集，为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		空集是其他任意集合（包括空集）的子集；
	 *		因此，如果由当前的 HashSet(T) 表示的集合为空，此方法返回 true，即使 other 参数为空集也是如此。
	 *		如果 count 大于 other 中元素的个数，则此方法始终返回 false。
	 *		此方法的运算复杂度是 O(n)。
	 */
	public final bool isSubsetOf(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(theSize == 0)
			return true;
		if(theSize > other.count)
			return false;
		return checkIsSubsetOf(other);
	}

	/**
	 * 确定 HashSet(T) 是否为指定集合的真超集。
	 * Params:
	 *		other = 要进行比较的集合。
	 * Returns:
	 *		如果 HashSet(T) 是 other 的真超集，为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Comments:
	 *		空集是其他任意集合（包括空集）的真超集；
	 *		因此，如果由当前的 HashSet(T) 表示的集合为空，此方法返回 true，即使 other 参数为空集也是如此。
	 *		如果 count 小于或等于 other 中元素的个数，则此方法始终返回 false。
	 *		此方法的运算复杂度是 O(n)。 
	 */
	public final bool isProperSupersetOf(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(other.count == 0)
			return true;
		if(theSize <= other.count)
			return false;
		return checkIsSupersetOf(other);
	}

	/**
	 * 确定此 HashSet(T) 是否为指定集合的超集。
	 * Params:
	 *		other = 要进行比较的集合。
	 * Throws:
	 *		AssertError，当 other 为 null 时。
	 * Returns:
	 *		如果 HashSet(T) 是 other 的超集，为 true；否则为 false。
	 * Comments:
	 * 		空集是其他任意集合（包括空集）的超集。
	 *		因此，如果由 other 参数表示的集合为空，则此方法将返回 true，即使当前的 HashSet(T) 为空也是如此。 
	 *		如果 count 小于 other 中元素的个数，则此方法始终返回 false。
	 *		此方法的运算复杂度是 O(n)。
	 */
	public final bool isSupersetOf(ICollection!(T) other)
	in
	{
		assert(other !is null);
	}
	body
	{
		if(other.count == 0)
			return true;
		if(theSize < other.count)
			return false;
		return checkIsSupersetOf(other);
	}

	/**
	 * 获取该 Set 使用的相等比较器。
	 */
	public final IEqualityComparer!(T) comparer()
	{
		return theComparer;
	}

	private bool checkIsSupersetOf(ICollection!(T) other)
	{
		foreach(item; other)
		{
			if(!contains(item))
				return false;
		}
		return true;
	}

	private bool checkIsSubsetOf(ICollection!(T) other)
	{
		foreach(item; this)
		{
			if(!other.contains(item))
				return false;
		}
		return true;
	}
	
	private void initialize(int size)
	{
		auto newSize = PrimeHelper.getNextPrime(size);
		theBuckets = new int[newSize];
		theSlots = new Slot[newSize];
	}

	private void resize()
	{
		int newSize = theSize * 2;
		if(newSize < 0)
			newSize = theSize;
		auto prime = PrimeHelper.getNextPrime(newSize);
		if(prime <= theSize)
			throw new ArgumentException("The set is overflow.");
		if(theSlots !is null)
		{
			theSlots.length = prime;
		}
		auto newBuckets = new int[prime];
		for(auto i = 0; i < theFreeSize; i++)
		{
			auto index = theSlots[i].hashCode % prime;
			theSlots[i].next = newBuckets[index] - 1;
			newBuckets[index] = i + 1;
		}
		delete theBuckets;
		theBuckets = newBuckets;
	}

	private hash_t hashOf(T item)
	{
		static if(IsReferenceType!(T))
		{
			if(item is null)
				return 0;
		}
		return theComparer.toHash(item) & int.max;
	}

	private int indexOf(T item)
	{
		auto hash = hashOf(item);
		auto index = hash % theBuckets.length;
		for(auto i = theBuckets[index] - 1; i >= 0; i = theSlots[i].next)
		{
			if((theSlots[i].hashCode == hash) && (theComparer.equals(theSlots[i].value, item)))
			{
				return i;
			}
		}
		return -1;
	}
}

package class HashSetEqualityComparer(T) : IEqualityComparer!(HashSet!(T))
{
	private IEqualityComparer!(T) theComparer;

	public this(IEqualityComparer!(T) comparer = DefaultEqualityComparer!(T).getInstance())
	in
	{
		assert(comparer !is null);
	}
	body
	{
		theComparer = comparer;
	}

	public override bool opEquals(Object obj)
	{
		auto comparer = cast(HashSetEqualityComparer!(T))obj;
		
		if(comparer is null)
			return false;

		return theComparer == comparer.theComparer;
	}

	public bool opEquals(HashSetEqualityComparer!(T) comparer)
	{
		if(comparer is null)
			return false;

		return theComparer == comparer.theComparer;
	}

	public override hash_t toHash()
	{
		return HashHelper.toHash(theComparer);
	}

	public bool equals(HashSet!(T) x, HashSet!(T) y)
	{
		if(x is null)
			return y is null;
		if(y is null)
			return false;
		if(x.comparer == y.comparer)
		{
			if(x.count != y.count)
				return false;
			foreach(item; y)
			{
				if(!x.contains(item))
					return false;
			}
			return true;
		}
		foreach(item; y)
		{
			bool result = false;
			foreach(value; x)
			{
				if(theComparer.equals(item, value))
				{
					result = true;
					break;
				}
			}
			if(!result)
				return false;
		}

		return true;
	}

	public hash_t toHash(HashSet!(T) set)
	{
		int result = 0;
		if(set !is null)
		{
			foreach(item; set)
			{
				result ^= theComparer.toHash(item) & int.max; 
			}
		}
		return result;
	}
}

unittest
{
	class TestHashSet
	{
		void testAdd()
		{
			auto set = new HashSet!(int)();
			assert(set.add(1));
			assert(set.add(2));
			assert(set.add(3));
			assert(set.count == 3);
			assert(!set.add(3));
			assert(!set.add(2));
			assert(!set.add(1));
		}

		void testMassiveAdd()
		{ 
			auto set = new HashSet!(int)(10000);
			for(auto i = 0; i < 10000; i++)
			{
				assert(set.add(i));
			}

			assert(set.count == 10000);
		}

		void testRemove()
		{
			auto set = new HashSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);
			set.add(4);
			assert(set.remove(2));
			assert(set.remove(3));
			assert(set.count == 2);
			assert(set.contains(1));
			assert(set.contains(4));
			assert(!set.contains(2));
			assert(!set.contains(3));
		}

		void testMassiveRemove()
		{
			auto set = new HashSet!(int)(10000);
			for(auto i = 0; i < 10000; i++)
			{
				set.add(i);
			}

			for(auto i = 0; i < 10000; i++)
			{
				assert(set.remove(i));
			}

			assert(set.isEmpty());
		}

		void testToArray()
		{
			auto set = new HashSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);
			int[3] array = void;
			set.toArray(array);
			for(auto i = 0; i < array.length; i++)
			{
				assert(set.contains(array[i]));
			}
		}

		void testClear()
		{
			auto set = new HashSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);
			set.clear();
			assert(set.isEmpty());
		}

		void testContains()
		{
			auto set = new HashSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);

			assert(set.contains(1));
			assert(set.contains(2));
			assert(set.contains(3));
		}

		void testForEach()
		{
			auto set = new HashSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);

			try
			{
				foreach(item; set)
				{
					set.add(4);
				}
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}
		}

		void testRemoveWhere()
		{
			auto set = new HashSet!(int)();
			set.add(1);
			set.add(2);
			set.add(3);

			set.removeWhere(delegate bool(int i){return i <= 2;});

			assert(set.count == 1);
		}

		void testOverlaps()
		{
			auto list = new ArrayList!(int)();
			list.add(1);
			list.add(2);
			auto set = new HashSet!(int)();
			set.add(2);

			assert(set.overlaps(list));
		}

		void testIntersectWith()
		{
			auto list = new ArrayList!(int)();
			auto set = new HashSet!(int)();
			
			list.add(1);
			list.add(2);
			list.add(3);
			list.add(4);

			set.add(3);
			set.add(4);

			set.intersectWith(list);

			assert(set.count == 2);
			assert(set.contains(3));
			assert(set.contains(4));
			assert(!set.contains(1));
			assert(!set.contains(2));
		}

		void testExceptWith()
		{
			auto list = new ArrayList!(int)();
			auto set = new HashSet!(int)();
			
			list.add(1);
			list.add(2);
			list.add(3);
			list.add(4);

			set.add(3);
			set.add(4);

			set.exceptWith(list);

			assert(set.count == 0);
			assert(!set.contains(1));
			assert(!set.contains(2));
			assert(!set.contains(3));
			assert(!set.contains(4));
		}

		void testUnionWith()
		{
			auto list = new ArrayList!(int)();
			auto set = new HashSet!(int)();
			
			list.add(1);
			list.add(2);
			list.add(3);
			list.add(4);

			set.add(3);
			set.add(4);
			set.add(5);

			set.unionWith(list);

			assert(set.count == 5);
			assert(set.contains(1));
			assert(set.contains(2));
			assert(set.contains(3));
			assert(set.contains(4));
			assert(set.contains(5));
		}

		void testSymmetricExceptWith()
		{
			auto list = new ArrayList!(int)();
			auto set = new HashSet!(int)();
			
			list.add(1);
			list.add(2);
			list.add(3);
			list.add(4);

			set.add(3);
			set.add(4);

			set.symmetricExceptWith(list);

			assert(set.count == 2);
			assert(set.contains(1));
			assert(set.contains(2));
		}

		void testSubsetOf()
		{
			auto set = new HashSet!(int)();
			auto list = new ArrayList!(int)();
			
			assert(set.isSubsetOf(list));

			list.add(1);
			list.add(2);

			assert(set.isSubsetOf(list));

			set.add(1);
			set.add(2);

			list.add(3);

			assert(set.isSubsetOf(list));

			set.add(3);
			
			assert(!set.isProperSubsetOf(list));
		}

		void testSupersetOf()
		{
			auto set = new HashSet!(int)();
			auto list = new ArrayList!(int)();
			set.add(1);
			set.add(2);
			set.add(3);
			list.add(1);
			list.add(2);

			assert(set.isSupersetOf(list));
			list.add(4);
			assert(!set.isSupersetOf(list));
			list.remove(4);
			assert(set.isProperSupersetOf(list));
			list.add(3);
			assert(!set.isProperSupersetOf(list));
		}

		void testSetEquals()
		{
			auto set = new HashSet!(int)();
			auto list = new ArrayList!(int)();
			set.add(1);
			set.add(2);
			set.add(3);
			list.add(1);
			list.add(2);

			assert(!set.setEquals(list));

			list.add(3);
			assert(set.setEquals(list));
		}
	}

	auto test = new TestHashSet();
	test.testAdd();
	test.testMassiveAdd();
	test.testRemove();
	test.testMassiveRemove();
	test.testToArray();
	test.testClear();
	test.testContains();
	test.testForEach();
	test.testRemoveWhere();
	test.testOverlaps();
	test.testIntersectWith();
	test.testExceptWith();
	test.testUnionWith();
	test.testSymmetricExceptWith();
	test.testSubsetOf();
	test.testSupersetOf();
	test.testSetEquals();
}